package com.gjx.leetcode;

import java.util.ArrayList;
import java.util.List;

//60. 第k个排列
//
//给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
//
//按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
//
//"123"
//"132"
//"213"
//"231"
//"312"
//"321"
//给定 n 和 k，返回第 k 个排列。
//
//说明：
//
//给定 n 的范围是 [1, 9]。
//给定 k 的范围是[1,  n!]。
//示例 1:
//
//输入: n = 3, k = 3
//输出: "213"
//示例 2:
//
//输入: n = 4, k = 9
//输出: "2314"


public class Solution060 {
	public String getPermutation(int n, int k) {
   
		List<Character> list = new ArrayList<>();
		for (int i=1; i<=n; i++) {
			list.add((char) (i+'0'));
		}
		
		StringBuilder sb = new StringBuilder();
		
		int group = 1;
		for (int i=1; i<n; i++) {
			group *= i;
		}
		
		
		while(k > 1) {
			int part = (k - 1) / group;
			sb.append(list.get(part));
			list.remove(part);
			k -= group * part;
			group /= (n-1);
			n--;
		}
		
		for (char c : list) {
			sb.append(c);
		}
		
		return sb.toString();
    }
	
	public static void main(String[] args) {
		new Solution060().getPermutation(4, 7);
	}
}
